home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C ++ / Applications / TimGA 1.2.1 / .cp / CEdge.cp < prev    next >
Encoding:
Text File  |  1997-07-16  |  4.5 KB  |  136 lines  |  [TEXT/CWIE]
  1. // ===========================================================================
  2. //    CEdge.cp            ©1995-97 Timo Eloranta        All rights reserved.
  3. // ===========================================================================
  4. //    A simple edge class. Most functions in the header (inlined).
  5.  
  6. #include "CEdge.h"
  7. #include "MyUtils.h"
  8.  
  9. #include <algobase.h>    // MSL - min & max
  10.  
  11. // ---------------------------------------------------------------------------
  12. //        • Intersects
  13. //
  14. //          Called by:    CGraphDrawing::SimpleCountSect
  15. //                        CGraphDrawing::SmarterCountSect
  16. // ---------------------------------------------------------------------------
  17. //    Return true if this edge intersects the given edge (inEdge).
  18. //    Otherwise return false. If you know how this function could be
  19. //    improved, please let me know, since TimGA uses this function A LOT...
  20.  
  21. Boolean 
  22. CEdge::Intersects( const CEdge & inEdge) const
  23. {
  24.     Int16    p1x, p2x, p3x, p4x, xMin12, xMax12, xMin34, xMax34,
  25.             p1y, p2y, p3y, p4y, yMin12, yMax12, yMin34, yMax34;
  26.  
  27.     // p1x and p1y are the x- and y-coordinates of this edge's 1st node
  28.     // p2x and p2y are the x- and y-coordinates of this edge's 2nd node
  29.     // ...
  30.             
  31.     mNode1 ->            GetNodePos( p1x, p1y );
  32.     mNode2 ->            GetNodePos( p2x, p2y );
  33.     
  34.     inEdge.mNode1 ->    GetNodePos( p3x, p3y );
  35.     inEdge.mNode2 ->    GetNodePos( p4x, p4y );
  36.     
  37.     //
  38.     //     Stage 1: Quick Rejection Test
  39.     //
  40.     //         Line segments cannot intersect if their 
  41.     //        bounding boxes do not intersect
  42.     //
  43.     
  44.     if ( (xMax12 = max(p1x, p2x)) < (xMin34 = min(p3x, p4x)) || 
  45.          (xMax34 = max(p3x, p4x)) < (xMin12 = min(p1x, p2x)) || 
  46.          (yMax12 = max(p1y, p2y)) < (yMin34 = min(p3y, p4y)) || 
  47.          (yMax34 = max(p3y, p4y)) < (yMin12 = min(p1y, p2y)) )
  48.         return false; 
  49.  
  50.     //  The following is my own addition to the quick
  51.     //  rejection phase resulting from the fact that I don't
  52.     //  consider it an intersection if two edges share an
  53.     //  endpoint (node) but have no other shared points.
  54.     
  55.     if ( ( xMax12 == xMin34 && xMin12 < xMax12 && xMin34 < xMax34 ) ||
  56.          ( xMin12 == xMax34 && xMin12 < xMax12 && xMin34 < xMax34 ) ||
  57.          ( yMax12 == yMin34 && yMin12 < yMax12 && yMin34 < yMax34 ) ||
  58.          ( yMin12 == yMax34 && yMin12 < yMax12 && yMin34 < yMax34 ) )
  59.         return false;
  60.  
  61.     //
  62.     //     Stage 2: Determining whether both segments straddle
  63.     //             the line containing the other
  64.     //
  65.     //              See pp. 889-890 in "Introduction to Algorithms" 
  66.     //             by Cormen, Leiserson and Rivest (1990)
  67.     //
  68.     
  69.     //  First we'll test if the segment with endpoints p3 and p4
  70.     //  straddles the line containing the points p1 and p2
  71.     
  72.     Int32    crossp1 =    ((p3x - p1x) * (p2y - p1y)) -
  73.                         ((p2x - p1x) * (p3y - p1y));
  74.     Int32    crossp2 =    ((p4x - p1x) * (p2y - p1y)) -
  75.                         ((p2x - p1x) * (p4y - p1y));
  76.  
  77.     Int32    crossp12 = crossp1 * crossp2;
  78.  
  79.     // Are the signs of the cross products different?
  80.     
  81.     if ( crossp12 > 0 )                    // Segment does not straddle
  82.          return false;                    // We are done!
  83.  
  84.     if ( crossp1 == 0 && crossp2 == 0)    // Segments are collinear
  85.         return true;                    // and must intersect...
  86.  
  87.     // Next we'll handle the case where other of the cross products
  88.     // equals zero (but not both). This means that either p3 or p4 is on
  89.     // the same line as both p1 and p2. *I* do not count this as straddling
  90.     // if the point in question is an endpoint of both edges...
  91.  
  92.     if ( crossp12 == 0 && HasMutualNode( inEdge ) )
  93.         return false;
  94.  
  95.     // If we are still here, segment with points p3 and p4 does straddle
  96.     // the line containing points p1 and p2. For the segments to intersect
  97.     // also the segment with p1 and p2 must straddle the line containing
  98.     // points p3 and p4...
  99.  
  100.     crossp1 =    ((p1x - p3x) * (p4y - p3y)) -
  101.                 ((p4x - p3x) * (p1y - p3y));
  102.     crossp2 =    ((p2x - p3x) * (p4y - p3y)) -
  103.                 ((p4x - p3x) * (p2y - p3y));
  104.  
  105.     crossp12 = crossp1 * crossp2;
  106.  
  107.     if ( crossp12 > 0 ) return false;    // Segment does not straddle
  108.     if ( crossp12 < 0 ) return true;    // Segment straddles
  109.  
  110.     return (! HasMutualNode( inEdge ));
  111. }
  112.  
  113. // ---------------------------------------------------------------------------
  114. //        • Draw
  115. //
  116. //          Called by:    CGraphDrawing::DrawEdges
  117. // ---------------------------------------------------------------------------
  118. //    Draw this edge.
  119.  
  120. void 
  121. CEdge::Draw( 
  122.     Int16 inOneOneXY,                 // The x- and y-coordinate of the 
  123.                                     // centerpoint of the (1,1) square
  124.     Int16 inSquareSize ) const        // The size of a square in pixels
  125. {
  126.     Int16    p1x, p2x, p1y, p2y;
  127.             
  128.     mNode1 -> GetNodePos( p1x, p1y );
  129.     mNode2 -> GetNodePos( p2x, p2y );
  130.  
  131.     LineFromTo (    inOneOneXY + (p1x - 1) * inSquareSize, 
  132.                     inOneOneXY + (p1y - 1) * inSquareSize, 
  133.                     inOneOneXY + (p2x - 1) * inSquareSize, 
  134.                     inOneOneXY + (p2y - 1) * inSquareSize    );
  135. }
  136.